package bfs;


//正难则反： 从海洋到陆地 -> 但不好扩，因为需要返回到起始层的信息
//         改成从陆地到海洋 -> 返回最大的层即可；
public class 地图分析 {
	public int l,r;
    public int MAXM=101;
    public int MAXN=101;
    public int[] dx={0,0,1,-1};
    public int[] dy={1,-1,0,0};
    public int[][] queue=new int[MAXM*MAXN][2];
    public boolean[][] visit=new boolean[MAXM][MAXN];
    public int maxDistance(int[][] grid) {
        l=r=0;
        int seas=0;
        int m=grid.length;
        int n=grid[0].length;
        //1.找到所有的陆地并入队列 2.清除上一轮数据的影响
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(grid[i][j]==1){
                    queue[r][0]=i;
                    queue[r++][1]=j;
                    visit[i][j]=true;
                }
                else{
                    visit[i][j]=false;
                    seas++;
                }
            }
        }
        //由题知，没有海洋或者全为海洋直接返回-1
        if(seas==0||seas==m*n){
            return -1;
        }
        //bfs过程
        int level=0;
        while(l<r){
            level++;
            int size=r-l;
            //遍历该层的所有节点
            for(int i=0;i<size;i++){
                int x=queue[l][0];
                int y=queue[l++][1];
                //将一个节点的四周标记并入队列
                for(int k=0;k<4;k++){
                    int nx=x+dx[k],ny=y+dy[k];
                    //为什么此处未判断是否为海洋在扩，如果是陆地呢？
                    //实际上，不可能是陆地，如果前面已经将所有的陆地入队列并标记了，
                    //因此，除了一开始陆地在队列中，后续加入的一定是海洋；
                    //(因为只有海洋才为false)
                    if(nx>=0&&ny>=0&&nx<m&&ny<n&&visit[nx][ny]==false){
                        queue[r][0]=nx;
                        queue[r++][1]=ny;
                        visit[nx][ny]=true;
                    }
                }
            }
        }
        return level-1;
    }
}
